/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/first-missing-positive
   @Language: C++
   @Datetime: 16-02-09 05:52
   */

class Solution {
public:
	/**    
	 * @param A: a vector of integers
	 * @return: an integer
	 */
	/** Tips: find first missing positive number
	 * we can store the positive number which range [1,n] to A[0]~A[n-1]
	 * then search from A[0] to end, the first non-positive number is answer
	 * */
	int firstMissingPositive(vector<int> A) {
		// write your code here
		for(int i=0; i<A.size();){  
			if(A[i]==i+1 ||
					!(A[i]>0 && A[i]<=A.size() && A[A[i]-1]!=A[i])) ++i;
			else swap(A[i], A[A[i]-1]);
		}
		// find the first non-positive number
		for(int i=0; i<A.size(); ++i)  
			if(A[i] != i+1) return i+1;  
		return A.size()+1; 
	}
};
